package com.ctgu.蓝桥杯真题.B组2020第2场;

/**
 * @author: Backdiy
 * @data: 2021/4/8 19:27
 * @desc:
 */

public class D七段码 {
    static int[] bin;//并查集数组
    static int[][] arr;//记录相邻关系
    static boolean[] key;//记录该编号的灯泡是否已经被选
    static int ans;

    public static void main(String[] args) {
        arr = new int[8][8];//赋值为1表示两个编号的灯泡是相邻的，具有连通的条件
        arr[1][2] = 1;
        arr[1][6] = 1;
        arr[2][1] = 1;
        arr[2][3] = 1;
        arr[2][7] = 1;
        arr[3][4] = 1;
        arr[3][7] = 1;
        arr[3][2] = 1;
        arr[4][3] = 1;
        arr[4][5] = 1;
        arr[5][4] = 1;
        arr[5][6] = 1;
        arr[5][7] = 1;
        arr[6][1] = 1;
        arr[6][7] = 1;
        arr[6][5] = 1;
        arr[7][2] = 1;
        arr[7][6] = 1;
        arr[7][5] = 1;
        arr[7][3] = 1;
        int[] record = new int[8];
        key = new boolean[8];
        dfs(0, 0, record);
        System.out.println(ans);
    }

    /**
     * 该方法为并查集的寻找根节点的方法
     *
     * @param x 返回该编号结点的祖宗结点
     * @return
     */
    private static int find(int x) {
        if (x == bin[x]) return x;
        return bin[x] = find(bin[x]);
    }

    /**
     * @param cur    记录当前被挑中的灯管的编号
     * @param max    当前被挑选的灯泡的最大编号
     * @param record 目前已经被选中的灯泡编号的集合
     */
    private static void dfs(int cur, int max, int[] record) {
        if (judge(record, cur)) ans++;
        for (int i = max + 1; i <= 7; i++) {
            if (!key[i]) {
                key[i] = true;
                record[cur] = i;
                dfs(cur + 1, i, record);
                key[i] = false;
            }
        }
    }

    /**
     * 该方法的作用是判断当前集合是否满足相邻
     *
     * @param now 当前被挑选的灯泡的集合
     * @param cur 当前集合中灯泡的数目
     * @return
     */
    public static boolean judge(int[] now, int cur) {
        int cnt = cur - 1;//使得所有的点刚好连通的最少边的数目等于点的数目减一，因此我们需要判断能否构建这么多的边
        bin = new int[8];
        //初始化并查集数组
        for (int i = 0; i < 8; i++) {
            bin[i] = i;
        }
        for (int i = 0; i < cur; i++) {
            for (int j = i + 1; j < cur; j++) {
                if (find(now[i]) != find(now[j]) && arr[now[i]][now[j]] == 1)//若两个点互不联通
                {
                    cnt--;//构建一条边，还需要构建的边数减一
                    bin[find(now[i])] = bin[find(now[j])];//构建边
                }
            }
        }
        if (cnt == 0) return true;//刚好构建完成则返回true
        return false;
    }
}
